#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#define ERROR 0
#define OK 1
typedef int ElemType;
typedef struct Node /*结点类型定义*/
{
    ElemType data;
    struct Node *next;
} Node, *LinkList; /*LinkList为结构指针类型*/

LinkList InitList() /*初始化单链表*/
{
    LinkList L;
    L = (LinkList)malloc(sizeof(Node));
    L->next = NULL;
    return L;
}

void ClearList(LinkList L) /*清空单链表*/
{
    //清空单链表的代码
    LinkList p, q;
    p = L->next;
    while (p != NULL)
    {
        q = p->next;
        free(p);
        p = q;
    }
    L->next = NULL;
}

int EmptyList(LinkList L) /*检查单链表是否为空*/
{
    if (L->next == NULL)
        return OK;
    //如果不为空
    else
        return ERROR;
}

void ListTraverse(LinkList L) /*遍历单链表*/
{
    Node *p;
    p = L->next;
    if (p == NULL)
        printf("单链表为空表\n");
    else
    {
        printf("单链表中的元素为：\n");
        while (p != NULL)
        {
            //打印
            printf("%5d ", p->data);
            p = p->next;
        }
        printf("\n");
    }
}

int ListLength(LinkList L) /*求单链表长度*/
{
    Node *p;
    int j;
    p = L->next;
    j = 0;
    while (p != NULL)
    {
        j++;
        p = p->next;
    }
    return j;
}

LinkList Getdata(LinkList L, int i) /*求单链表第i个元素*/
{
    Node *p;
    int j;
    p = L->next;
    j = 1;
    while (p != NULL && j < i)
    {
        j++;
        p = p->next;
    }
    //如果
    if (p != NULL) //不确定
        return p;
    else
        return NULL;
}

int Locate(LinkList L, ElemType e) /*查找单链表是否有元素e*/
{
    Node *p;
    int j;
    p = L->next;
    j = 1;
    while (p != NULL && p->data != e)
    {
        j++;
        p = p->next;
    }
    if (p != NULL)
        return j;
    else
        return 0;
}

void InsList(LinkList L, int i, ElemType e)
{ /*在带头结点的单链表L中第i个结点之前插入值为e的新结点。*/
    Node *pre, *s;
    int k = 0;
    pre = L;
    while (pre != NULL && k < i - 1)
    /*先找到第i-1个数据元素的存储位置,使指针Pre指向它*/
    {
        pre = pre->next;
        k = k + 1;
    }
    if (pre == NULL)
    {
        printf("插入位置不合理！");
        return;
    }
    s = (Node *)malloc(sizeof(Node)); /*为e申请一个新的结点*/
    s->data = e;                      //将待插入结点的值e赋给s的数据域
    s->next = pre->next;              //将待插入结点的值e赋给s的数据域
    pre->next = s;
}

int DelList(LinkList L, int i, ElemType *e)
/*在带头结点的单链表L中删除第i个元素，并保存其值到变量*e中*/
{
    Node *p, *r;
    int k = 0;
    p = L;
    while (p->next != NULL && k < i - 1) /*寻找被删除结点i的前驱结点*/
    {
        p = p->next;
        k = k + 1;
    }
    if (p->next == NULL) /* 即while循环是因为p->next=NULL而跳出的*/
    {
        printf("删除结点的位置i不合理！");
        return ERROR;
    }
    r = p->next;
    //删除结点r
    p->next = r->next; /*删除结点r*/
    *e = r->data;
    free(r); /*释放被删除的结点所占的内存空间*/
    return OK;
}

LinkList CreateList()
{
    LinkList L;
    Node *r, *s;
    ElemType x;
    int flag = -1;
    L = (LinkList)malloc(sizeof(Node));
    L->next = NULL;
    r = L;
    printf("请输入序列，输入-1结束\n");
    scanf("%d", &x);
    while (x != flag)
    {
        s = (Node *)malloc(sizeof(Node));
        s->data = x;
        r->next = s;
        r = s;
        scanf("%d", &x);
    }
    r->next = NULL;
    return L;
}
void PrintList(LinkList L) /*输出单链表中的结点*/
{
    Node *p;
    p = L->next;
    while (p != NULL)
    {
        printf("%5d", p->data);
        p = p->next;
    }
    printf("\n");
}
int scan()
{
    int d;
    printf("请选择所要进行的操作\n");
    printf("1.初始化　2.清空 3.求单链表长度 4.检查单链表是否为空\n");
    printf("5.遍历单链表　6.从单链表中查找元素 \n");
    printf("7.从单链表中查找与给定元素值相同的元素在单链表中的位置\n");
    printf("8.向单链表中插入元素 9.从单链表中删除元素\n");
    printf("其它键退出\n");
    scanf("%d", &d);
    return d;
}
int main()
{
    int quit = 0;
    int i, location;
    ElemType e;
    LinkList L;
    Node *p;
    L = CreateList();
    switch (scan())
    {
    case 1:
        InitList();
        break;
    case 2:
        ClearList(L);
        break;
    case 3:
        printf("单链表的长度为%d\n", ListLength(L));
        break;
    case 4:
        if (EmptyList(L) == OK)
            printf("单链表为空\n");
        else
            printf("单链表不为空\n");
        break;
    case 5:
        ListTraverse(L);
        break;
    case 6:
        printf("请输入待查找的元素在单链表中的位置\n");
        scanf("%d", &i);
        p = Getdata(L, i);
        if (p != NULL)
            printf("单链表中第%d个元素的值为:%d\n", i, p->data);
        else
            printf("查找位置不正确\n");
        break;
    case 7:
        printf("请输入待查找的元素的值\n");
        scanf("%d", &e);
        location = Locate(L, e);
        if (location)
            printf("%d在单链表中的位置为:%d\n", e, location);
        else
            printf("单链表中不存在值为%d的元素\n", e);
        break;
    case 8:
        printf("请输入待插入元素的位置和值（中间以空格或回车分隔）:\n");
        scanf("%d%d", &i, &e);
        InsList(L, i, e);
        PrintList(L);
        break;
    case 9:
        if (ListLength(L) == 0)
            printf("单链表已经为空，不能删除\n");
        else
        {
            printf("请输入待删除的元素的位置:\n");
            scanf("%d", &i);
            DelList(L, i, &e);
        }
        PrintList(L);
        break;
    default:
        quit = 1;
    }
    return 0;
}